/*
题目: 不同的子序列
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。
https://leetcode.cn/problems/distinct-subsequences/
 */
public class NumDistinct {
    // 滚动数组优化
    public int numDistinct(String s, String t) {
        int slen = s.length();
        int tlen = t.length();

        // dp[i][j] 表示 s[:i] 包含 t[:j] 子序列的个数
        int[] dp = new int[tlen + 1];
        dp[0] = 1; // 空集属于空集

        for (int i = 1; i <= slen; i ++) {
            dp[0] = 1;  // 初始化
            for (int j = tlen; j >= 1; j --) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) { // 如果相等, 可以用或者不用
                    //            用 s[i]          不用 s[j]
                    dp[j] = dp[j - 1] + dp[j];
                } else {
                    dp[j] = dp[j];
                }
            }
        }

        return dp[tlen];
    }

    // 动归二维
    public int numDistinctBase(String s, String t) {
        int slen = s.length();
        int tlen = t.length();

        // dp[i][j] 表示 s[:i] 包含 t[:j] 子序列的个数
        int[][] dp = new int[slen + 1][tlen + 1];
        dp[0][0] = 1; // 空集属于空集

        for (int i = 1; i <= slen; i ++) {
            dp[i][0] = 1;  // 初始化
            for (int j = 1; j <= tlen; j ++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) { // 如果相等, 可以用或者不用
                    //            用 s[i]          不用 s[j]
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[slen][tlen];
    }
}
